Ý tưởng về việc sắp xếp một danh sách để tìm kiếm được nhanh hơn đã có từ thời cổ xưa. Ví dụ được biết tới sớm nhất là tấm bảng của Inakibit-Anu từ thời Babylon vào k. 200 TCN. Tấm bảng này chứa khoảng 500 con số ở hệ thập lục phân và các số nghịch đảo của chúng được sắp xếp theo thứ tự từ điển, khiến việc tìm kiếm dễ dàng hơn. Ngoài ra trên Quần đảo Aegean còn phát hiện được một vài danh sách những cái tên được sắp xếp theo chữ cái đầu tiên. Catholicon, một cuốn từ điển Latin được hoàn thành vào năm 1286 SCN, là tác phẩm đầu tiên mô tả các quy tắc sắp xếp các từ theo thứ tự bảng chữ cái, thay vì chỉ theo vài ký tự đầu tiên.[10]

Vào năm 1946, John Mauchly là người đầu tiên nhắc tới tìm kiếm nhị phân trong Moore School Lectures, một khóa học về máy tính tại Trường Kỹ thuật Điện tử Moore, Đại học Pennsylvania.[59] Năm 1957, William Wesley Peterson xuất bản phương pháp đầu tiên cho giải thuật tìm kiếm nội suy.[10][60] Mọi thuật toán tìm kiếm nhị phân đã được xuất bản chỉ hoạt động với các mảng có độ dài ở dạng 2 α − 1 {\displaystyle 2^{\alpha }-1} [lower-alpha 8] cho tới năm 1960, khi Derrick Henry Lehmer cho xuất bản một thuật toán tìm kiếm nhị phân có thể hoạt động với mọi mảng.[62] Năm 1962, Hermann Bottenbruch trình bày thuật toán tìm kiếm nhị phân được áp dụng bằng ngôn ngữ ALGOL 60, trong đó bước kiểm tra phần tử giữa được đưa xuống cuối, làm tăng số phép lặp trung bình thêm một, nhưng giảm được một bước so sánh mỗi phép lặp.[9] Thuật toán uniform binary search được phát triển bởi A. K. Chandra tại Đại học Stanford vào năm 1971.[10] Năm 1986, Bernard Chazelle và Leonidas J. Guibas giới thiệu phương pháp đổ xuống một phần (fractional cascading) nhằm giải quyết nhiều vấn đề về tìm kiếm trong hình học tính toán.[48][63][64]